#include <algorithm>

#include "../common.h"

const int N = INT_MAX;
/*
 * 学习方法：
 * 1、上课讲模板
 * 2、理解并记忆模版，能写出来并且调试通过
 * 3、练习题目，应用模板，擦了重写，3~5次
 * /

/*
 * 快速排序 --- 分治
 * 1、确定分界点x: q[l],q[r],q[(l+r)/2],随机
 * 2、调整区间：左边都<=x，右边都>=x，注意等于x情况可以在两边
 * 3、递归处理，左右两段
 *
 */

void QuickSort(int q[], int l, int r)
{
 if (l >= r)
  return;

 const int x = q[l];
 int i = l - 1, j = r + 1;
 while (i < j) {
  do ++i; while (q[i] < x);
  do --j; while (q[j] > x);
  if (i < j) {
   swap(q[i], q[j]);
  }
 }
 QuickSort(q, l, j);
 QuickSort(q, j + 1, r);
}

int Run()
{
 int n;
 int arr[N];

 scanf("%d", &n);
 for (int i = 0; i < n; i++)
  scanf("%d", &arr[i]);

 sort(arr, arr + n);
 for (int i = 0; i < n; i++)
  printf("%d ", arr[i]);
}

/*
 * 归并排序 --- 分治
 * 1、确定分界点: mid = (l+r)/2
 * 2、递归排序left，right
 * 3、归并 --- 合二为一
 *
 */

void MergeSort(int arr[], int l, int r)
{
 if (l >= r) return;
 int mid = l + r >> 1;
 MergeSort(arr, l, mid);
 MergeSort(arr, mid + 1, r);
 int i = l, j = mid + 1, k = 0;
 int tmp[N];
 while (i <= mid && j <= r) {
  if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
  else tmp[k++] = arr[j++];
 }
 while (i <= mid) tmp[k++] = arr[i++];
 while (j <= r) tmp[k++] = arr[j++];
 for (int i = l, j = 0; i <= r; i++, j++) arr[i] = tmp[j];
}
